This invention relates generally to content addressable memories and specifically to generating a device index in a content addressable memory.
A content addressable memory (CAM) is a storage device that can be instructed to retrieve information based upon a comparison of a comparand word with data words stored in the CAM. FIG. 1 shows a CAM device 100 having an array of memory cells 102 and an associated priority logic circuit 104. The CAM array 102 includes k rows of memory cells. Each row of memory cells stores a CAM word, and is connected to the logic 104 via a corresponding match line ML. The priority logic circuit 104 includes well-known match logic, multiple match logic, and a priority encoder. During compare operations, the comparand word is received at appropriate input terminals of the CAM device 100 and then compared with the CAM words stored in the CAM array 102. For each CAM word that matches the comparand word, its corresponding match line ML is asserted to indicate the match condition.
In response to the asserted match line ML, the priority logic circuit 104 asserts a match flag MF, and outputs the index of the matching CAM word. If there are multiple matches, the priority logic circuit 104 asserts a multiple match flag MMF, and selects one of the matching CAM words to be output from the CAM device 100. When there are multiple matches, priority logic circuit 104 selects the highest priority match, which is typically defined as the matching CAM word that has the lowest CAM index, although other priority schemes may be used. The index of the highest priority match, the contents of the matched location, and other status information (e.g., skip bit, empty bit, and full flag, as well as the match and multiple match flags) may be output from the CAM device 100 to an output bus (not shown in FIG. 1).
FIG. 2 shows a conventional architecture 200 of the priority logic circuit 104. The priority logic circuit 200 includes n well-known match and priority encoding logic (MPL) circuits 202(1)-202(n), a control circuit 204, a multiplexer (MUX) 206, and a concatenation node 208. Each MPL circuit 202(1)-202(n) receives a corresponding set of match lines ML_1 to ML_n, respectively, where each match line set ML_1 to ML_n includes x match lines from the CAM array 102 (see also FIG. 1). In response to its corresponding set of match lines ML, each MPL circuit 202(1)-202(n) provides a respective match flag MF_1 to MF_n to the control circuit 204 via corresponding signal lines 208(1)-208(n). Also, although not shown in FIG. 2 for simplicity, each MPL circuit 202(1)-202(n) may provide a multiple match flag MMF to the control circuit 204.
If there is a match condition within its corresponding match line set ML, each MPL circuit 202(1)-202(n) provides the highest priority matching index I_1 to I_n, respectively, to the MUX 206 via corresponding index buses 210(1)-210(n). Each index I_1 to I_n, and thus each index bus 210(1)-210(n), is y=log2x bits wide. Using the match flags MF_1 to MF_n, the control circuit 204 identifies the highest priority MPL circuit 202(1)-202(n) that detects a match condition and, in response thereto, provides a select signal to the MUX 206 to select the index I from that MPL circuit 202 to provide as an input signal to the concatenation node 208. The control circuit 204 also generates an m-bit set ID that identifies the index of the highest priority match line set that has a match condition. The set ID is provided to the concatenation node 208, and concatenated therein as the most significant bits (MSB""s) to the index I received from the MUX 206 to form a z-bit device index I_dev, where z=y+m. The device index is the index or address of the highest priority match in the entire CAM array.
The priority logic circuit 200 of FIG. 2 requires a significant number of signal lines to carry each of the indexes I_1 to I_n from respective MPL circuits 202(1)-202(n) to the MUX 206. Because of the 2 dimensional spacial relationship between the MPL circuits 202 and the MUX 206, the index buses 210 from the MPL circuits 202 located farthest from the MUX 206 (e.g., MPL circuit 202(1), then MPL circuit 202(2), and so on), are quite long and occupy significant silicon area. For example, as illustrated in FIG. 2, the index buses 210(1)-210(n) each run in both the horizontal and vertical directions, where each index bus 210(1)-210(n) is routed past all subsequent MPL circuits 202 to reach the MUX 206. As the size of CAM devices increases, the number and length of the index buses 210 increases, thereby consuming even greater silicon area. Accordingly, it would be desirable to reduce the amount of silicon area occupied by the index buses 210.
A method and apparatus are disclosed that generate a device index in a CAM device. In accordance with the present invention, the match lines of a CAM array are grouped into a plurality of sets. The match lines within each set are provided to a corresponding match and priority encoding logic (MPL) circuit. Each MPL circuit includes an input index terminal connected to an index output terminal of a previous MPL circuit, and includes an index output terminal connected to the index input terminal of a next MPL circuit. In response to match signals provided by its corresponding match line set, each MPL circuit generates a match flag, a multiple match flag, and the index of the highest priority match for the set. The match flags and multiple match flags from each MPL circuit are provided to a control circuit. The last MPL circuit has an index output terminal connected to an index input terminal of the control circuit.
In response to the match flags, the control circuit generates a plurality of select signals, each of which is provided to a corresponding MPL circuit. In response to its corresponding select signal, each MPL circuit selectively provides either the set index generated therein or a input set index received from the previous MPL circuit to the next MPL circuit. The control circuit asserts the select signals in a manner such that the index from the highest priority match line set ripples through one or more of the MPL circuits to the control circuit. The control circuit also generates a set ID that identifies the highest priority matching set. The set ID is concatenated as the most significant bit(s) to the selected set index to form the device index.
By rippling the highest priority set index through the MPL circuits to the control circuit, present embodiments may significantly reduce the length of the index buses. Thus, rather than routing an index bus from each MPL circuit to the control circuit, present embodiments route index buses between adjacent MPL circuits. The reduction in index signal lines and signal line lengths achieved by present embodiments may advantageously reduce the silicon area occupied thereby.
In some embodiments, a hierarchical scheme may be used.